//给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 
//
// 说明: 叶子节点是指没有子节点的节点。 
//
// 示例: 
//给定如下二叉树，以及目标和 sum = 22， 
//
//               5
//             / \
//            4   8
//           /   / \
//          11  13  4
//         /  \    / \
//        7    2  5   1
// 
//
// 返回: 
//
// [
//   [5,4,11,2],
//   [5,8,4,5]
//]
// 
// Related Topics 树 深度优先搜索 
// 👍 289 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Java：路径总和 II
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P113_PathSumIi {
    public static void main(String[] args) {
        Solution solution = new P113_PathSumIi().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> list = new LinkedList<>();
            traverse(root, sum, res, list);
            return res;
        }

        public void traverse(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {
            if (root == null) {
                return;
            }

            list.add(root.val);
            sum -= root.val;
            if (sum == 0 && root.left == null && root.right == null) {
                res.add(new ArrayList<>(list));
                list.remove(list.size() - 1);
                return;
            }
            traverse(root.left, sum, res, list);
            traverse(root.right, sum, res, list);
            list.remove(list.size() - 1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
